// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Quicksort using the Lomuto partition scheme
namespace ConsoleApp1
{
    class Program
    {
        static List<string> quicksort(List<string> items)
        {
            // A single item does not need sorting
            if (items.Count <= 1)
            {
                return items;
            }
            else
            {
                // Set the pointer position and pivot to be the last item
                int pointer1;
                int pointer2 = 0;
                string pivot_value = items[items.Count - 1];
                string temp;
                // Partitioning step
                for (pointer1 = 0; pointer1 < items.Count; pointer1++)
                {
                    if (string.Compare(items[pointer1], pivot_value) < 0)
                    {
                        temp = items[pointer2];
                        items[pointer2] = items[pointer1];
                        items[pointer1] = temp;
                        pointer2 = pointer2 + 1;
                    }
                }
                // Put the pivot in position
                temp = items[pointer2];
                items[pointer2] = pivot_value;
                items[items.Count - 1] = temp;

                // Divide and conquer left and right of the pivot
                List<string> new_list = new List<string>();
                new_list.AddRange(quicksort(items.GetRange(0, pointer2)));
                new_list.Add(items[pointer2]);
                new_list.AddRange(quicksort(items.GetRange(pointer2 + 1, items.Count - 1 - pointer2)));
                return new_list;
            }
        }

        // Main program starts here
        static void Main(string[] args)
        {
            List<string> items = new List<string> { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            items = quicksort(items);
            Console.WriteLine(String.Join(", ", items));
        }
    }
}
